// 邻接矩阵
#ifndef MGRAPH_H
#define MGRAPH_H

// 最大的结点数
#define MAX_NUM 100
// 网结构中的不连通
#define INFINITY 65535
// 定义点和边的数据类型
typedef char VertexType;
typedef int EdgeType;
// 图的有向和无向类型
enum DirectType
{
	UN_DIRECT = 0,
	DIRECT = 1
};
// 图的权值类型（图或网）
enum WeightType
{
	TYPE_GRAPH = 0,
	TYPE_NET = 1
};

/**
 * 邻接矩阵数据结构
 * 图结构中用0和1代表不连通和连通
 * 网结构中具体数值为权值，INFINITY为不连通
 */
typedef struct
{
	VertexType vex[MAX_NUM];
	EdgeType edge[MAX_NUM][MAX_NUM];
	DirectType directType;
	WeightType weightType;
	int vexNum = 0, arcNum = 0;
} MGraph;

/**
 * 创建图
 * @param graph 传入图引用
 * @param directType 有向和无向类型
 * @param weightType 图或网
 */
void createGraph(MGraph &, DirectType, WeightType);

/**
 * 查找对应顶点的索引
 * @param u 传入顶点值
 * @return 返回该值顶点的索引，不存在返回-1
 */
int locateVex(MGraph &, VertexType);

/**
 * 判断v和w是否直接相连
 * @param graph 传入图引用
 * @param v 传入v的索引
 * @param w 传入w的索引
 * @return v与w连通返回1，否则返回0
 */
int isConnected(MGraph &, int, int);

/**
 * 返回某个点的第一个邻接点的索引
 * @param graph 传入图引用
 * @param v 传入顶点索引
 * @return 返回传入点的第一个邻接点，找不到则返回-1
 */
int firstAdjVex(MGraph &, int);

/**
 * 查找v相对于w的下一个邻接点
 * @param graph 传入图引用
 * @param v 传入顶点索引
 * @param w 传入邻接点索引
 * @return 返回v相对于w的下一个邻接点，若w是v的最后一个邻接点，则返回-1
 */
int nextAdjVex(MGraph &, int, int);

/**
 * 插入一个顶点
 * @param graph 传入图引用
 * @param u 传入插入顶点的值
 */
void insertVex(MGraph &, VertexType);

/**
 * 删除一个顶点
 * @param graph 传入图引用
 * @param v 待删除顶点索引
 */
void deleteVex(MGraph &, int);

/**
 * 插入一条弧
 * @param graph 待操作的图
 * @param v 待连接的起点顶点索引
 * @param w 待连接的终点顶点索引
 * @param weight 权值
 */
void insertArc(MGraph &, int, int, int);

/**
 * 删除一条弧
 * @param graph 待操作的图
 * @param v 待删除的起点顶点索引
 * @param w 待删除的终点顶点索引
 */
void deleteArc(MGraph &, int, int);

/**
 * 深度优先遍历-递归逻辑部分
 * @param graph 遍历的图
 * @param i 开始遍历的顶点的索引
 * @param visited 访问辅助数组，标识哪些点被访问
 * @param visit 遍历回调函数
 */
void DFS(MGraph &, int, int *, void(VertexType &));

/**
 * 深度优先遍历-起始部分
 * @param graph 遍历的图
 * @param visit 遍历回调函数
 */
void DFSTraverse(MGraph &, void(VertexType &));

/**
 * 广度优先遍历
 * @param graph 遍历的图
 * @param visit 遍历回调函数
 */
void BFSTraverse(MGraph &, void(VertexType &));

/**
 * 输出图
 * @param graph 待输出的图引用
 */
void printGraph(MGraph &);

#include "./mgraph.cpp"

#endif